Dalam dunia teori graf, sebuah Pohon adalah personifikasi arsitektur dari ketertiban. Berbeda dengan jaringan yang kacau di mana bisa ada beberapa jalur menuju tujuan yang sama, pohon menyediakan perjalanan tunggal dan unik antara dua titik manapun. Kendala struktural ini bukanlah batasan, melainkan dasar dari sistem hierarki—dari silsilah dewa Yunani kuno hingga struktur direktori pada sistem operasi modern.
1. Anatomi Sebuah Pohon
Sebelum hierarki ada, kita memiliki Pohon Bebas. Definisinya sederhana namun elegan:
Definisi 9.1.1
Sebuah (pohon bebas) $T$ adalah graf sederhana di mana untuk setiap dua simpul $v$ dan $w$, terdapat jalur sederhana yang unik dari $v$ ke $w$. Ini berarti graf tersebut baik bersifat terhubung dan bebas siklus (tidak ada siklus).
Ketika kita menunjuk satu simpul tertentu sebagai "asal", kita menciptakan sebuah Pohon Bersumbu. Transformasi ini memperkenalkan orientasi spasial, di mana hubungan didefinisikan berdasarkan jarak dan arah dari akar.
Kosa Kata Hierarki
Dalam sebuah pohon dengan akar $v_0$, pertimbangkan jalur sederhana $(v_0, v_1, \dots, v_n)$:
- Induk: Simpul $v_{n-1}$ adalah induk dari $v_n$.
- Anak: $v_n$ adalah anak dari $v_{n-1}$.
- Saudara kandung: Simpul-simpul yang memiliki induk yang sama.
- Leluhur: Semua simpul pada jalur dari akar ke $v_n$ (menghilangkan $v_n$ itu sendiri dalam beberapa konteks).
- Keturunan: Semua simpul yang memiliki $v$ sebagai leluhur.
Metrik Struktural
- Tingkat: Panjang jalur unik dari akar ke sebuah simpul. Akar itu sendiri berada pada Tingkat 0.
- Tinggi: Jumlah tingkat maksimum yang ada dalam pohon.
- Daun (Simpul Terminal): Simpul tanpa anak—ujung dari sebuah cabang.
- Simpul Internal (Cabang): Simpul yang memiliki setidaknya satu anak.
🎯 Konsep Utama: Subpohon
Sebuah subpohon adalah himpunan bagian dari sebuah pohon yang terdiri dari sebuah simpul dan semua keturunannya. Dalam sistem file, ini adalah folder dan setiap file/subfolder di dalamnya. Dalam Gambar 9.2.1, garis keturunan dari Kronos (Zeus, Poseidon, Hades, Ares) adalah subpohon dari Uranus.
2. Implementasi Dunia Nyata
Pohon bukan hanya abstraksi matematis. Mereka adalah tulang punggung dari organisasi:
- Sistem File Komputer: 'Drive' C: adalah akar; folder adalah simpul internal; file adalah daun.
- Diagram Administratif: CEO adalah akar; manajer adalah simpul internal; kontributor individu adalah daun.
- Rangka Keputusan: Menyelesaikan teka-teki seperti Instant Insanity atau menganalisis planaritas n-kubus sering melibatkan navigasi ruang status yang menyerupai pohon.